#!/usr/bin/env python3

arr = [23, 2, 5, 18, 67, 9, -3, 17, 25, 10]

# bubble sort
def bubble(arr):
    arr_len = len(arr)
    for i in range(arr_len-1):
        for j in range(arr_len-1-i):
            if arr[j] > arr[j+1]:
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    return arr

# select sort
def select_sort(arr):
    arr_len = len(arr)
    for i in range(arr_len-1):
        temp_min = arr[i]
        index = i
        for j in range(i+1, arr_len):
            if temp_min > arr[j]:
                temp_min = arr[j]
                index = j
        arr[index] = arr[i]
        arr[i] = temp_min
    return arr

# fake insert sort
def fake_insert_sort(arr):
    arr1 = [arr[0]]
    arr.remove(arr[0])
    while len(arr):
        v = arr[0]
        inserted = False
        if len(arr1) == 1:
            if v > arr1[0]:
                arr1.append(v)
            else:
                arr1.insert(0, v)
            inserted = True
        else:
            for i in range(len(arr1)-1):
                if v>=arr1[i] and v<arr1[i+1]:
                    arr1.insert(i+1, v)
                    inserted = True
                    break
        if not inserted:
            arr1.append(v)
        arr.remove(arr[0])
    return arr1

def insert_sort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex>=0 and arr[preIndex]>current:
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex+1] = current
    return arr
        

print("origin array: ", arr)
print("after bubble: ", bubble(arr))
print("after select: ", select_sort(arr))
print("after insert: ", insert_sort(arr))